This invention relates to a clipping process for clipping a two-dimensional subject figure such as a graphic primitive or image against a clip region bounded by a clip boundary of arbitrary shape, and to a clipping processor for executing this process.
Clipping is the process of modifying a subject figure by retaining the part disposed inside a given clip boundary and removing the part disposed outside the clip boundary. The subject figure may be a graphic image or a primitive element thereof, such as a line, polygon, circle, or bitmapped character. Clipping is extensively employed in computer graphics and image processing, in computer operating systems that display windows, and in printers such as laser printers.
The prior art in this field is described in Fundamentals of Interactive Computer Graphics by J. D. Foley and A. van Dam, published by the Addison Wesley Publishing Company in 1984. Two clipping algorithms are disclosed therein, one due to Sutherland and Hodgman and another due to Weiler and Atherton, both of which clip a subject polygon described by a vertex list against a polygonal clip boundary. Both algorithms trace around the border of the subject polygon to find its intersections with the clip boundary and construct a new vertex list comprising the intersections thus found, plus such vertices of the subject polygon or clip boundary as may be necessary. The clipped subject polygon is then converted from this new vertex list to a form suitable for output by a raster output device such as a printer or cathode-ray tube (CRT) display. Specifically, the clipped polygon is converted to the device coordinate system, then filled with pixels and stored as a pixel map in a drawing memory such as a refresh buffer or frame buffer.
One problem with the prior art is that the algorithms described above cannot be easily extended to the case in which the boundary of the subject figure, or the clip boundary, or both, is a high-order curve such as the cubic Bezier curves and spline curves frequently employed in computer graphics. Finding the intersections in this case requires the solution of high-order algebraic equations, a process which is difficult and time-consuming and not suitable for implementation in special-purpose hardware.
Approximating such curves by polygons does not help, because to achieve a reasonably close approximation, the approximating polygon must have a large number of vertices. Since the above algorithms test each edge of the subject polygon against each edge of the clip boundary, and compute the coordinates of each point of intersection, they take much time to process a long vertex list. If the number of vertices is reduced to shorten the processing time, the approximation becomes crude and the quality of the output image suffers.
Another problem with the prior art is its unsatisfactory performance in handling highly irregular polygonal clip boundaries. The source of this problem is again the inordinate time taken to process a long vertex list. Further problems arise when the clip boundary is a self-intersection polygon, or comprises two or more independent polygons: for example, when the clip region has interior holes. In this case complications are introduced by the need to decide between the inside and outside of the clip region, and to make this decision at each point of intersection.
A more fundamental problem is that the prior-art clipping process is unrelated to the raster output process. The clipping process is therefore completely distinct from the process of converting the clipped figure to the pixel form acceptable by a raster output device. Performing these two processes separately takes extra time, and requires separate processors.